package com.cango.student.algorithm.offer;

import java.util.ArrayDeque;

/**
 * 请定义一个队列并实现函数max得到队列里的最大值，要求函数max、push_back和pop_front的时间复杂度都是O(1)。
 * <p>
 * 利用一个双端队列来存储当前队列里的最大值以及之后可能的最大值
 * 在定义题目要求功能的队列时，除了定义一个队列data存储数值，还需额外用一个队列maxmium存储可能的最大值；
 * 此外，还要定义一个数据结构，用于存放数据以及当前的index值，用于删除操作时确定是否删除maxmium中最大值。
 */
public class QueueWithMax {
    // 存储数值
    private ArrayDeque<InternalData> data = new ArrayDeque<InternalData>();
    // 存储可能的最大值
    private ArrayDeque<InternalData> maximum = new ArrayDeque<InternalData>();

    // 用于存放数据以及当前的index值
    private class InternalData {
        int number;
        int index;

        public InternalData(int number, int index) {
            this.number = number;
            this.index = index;
        }
    }

    private int curIndex;

    public void push_back(int number) {
        InternalData curData = new InternalData(number, curIndex);
        data.addLast(curData);

        // 可能最大队列不为空，且最大队列队尾小于number
        while (!maximum.isEmpty() && maximum.getLast().number < number)
            maximum.removeLast(); // 删除队尾（小）
        // 添加队尾（大）
        maximum.addLast(curData);

        curIndex++;  //别漏了这句
    }

    public void pop_front() {
        if (data.isEmpty()) {
            System.out.println("队列为空，无法删除！");
            return;
        }
        InternalData curData = data.removeFirst();
        if (curData.index == maximum.getFirst().index)
            maximum.removeFirst();
    }

    public int max() {
        if (maximum == null) {
            System.out.println("队列为空，无法删除！");
            return 0;
        }

        return maximum.getFirst().number;
    }

    public static void main(String[] args) {
        QueueWithMax testQueue = new QueueWithMax();
        // {2}
        testQueue.push_back(2);
        System.out.println(testQueue.max() == 2);
        // {2, 3}
        testQueue.push_back(3);
        System.out.println(testQueue.max() == 3);
        // {2, 3, 4}
        testQueue.push_back(4);
        System.out.println(testQueue.max() == 4);
        // {2, 3, 4, 2}
        testQueue.push_back(2);
        System.out.println(testQueue.max() == 4);
        // {3, 4, 2}
        testQueue.pop_front();
        System.out.println(testQueue.max() == 4);
        // {4, 2}
        testQueue.pop_front();
        System.out.println(testQueue.max() == 4);
        // {2}
        testQueue.pop_front();
        System.out.println(testQueue.max() == 2);
        // {2, 6}
        testQueue.push_back(6);
        System.out.println(testQueue.max() == 6);
        // {2, 6, 2}
        testQueue.push_back(2);
        System.out.println(testQueue.max() == 6);
        // {2, 6, 2, 5}
        testQueue.push_back(5);
        System.out.println(testQueue.max() == 6);
        // {6, 2, 5}
        testQueue.pop_front();
        System.out.println(testQueue.max() == 6);
        // {2, 5}
        testQueue.pop_front();
        System.out.println(testQueue.max() == 5);
        // {5}
        testQueue.pop_front();
        System.out.println(testQueue.max() == 5);
        // {5, 1}
        testQueue.push_back(1);
        System.out.println(testQueue.max() == 5);
    }
}
